package com.sheng.leetcode.year2022.month11.day16;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2022/11/16
 *<p>
 * 775. 全局倒置与局部倒置<p>
 *<p>
 * 给你一个长度为 n 的整数数组 nums ，表示由范围 [0, n - 1] 内所有整数组成的一个排列。<p>
 * 全局倒置 的数目等于满足下述条件不同下标对 (i, j) 的数目：<p>
 * 0 <= i < j < n<p>
 * nums[i] > nums[j]<p>
 * 局部倒置 的数目等于满足下述条件的下标 i 的数目：<p>
 * 0 <= i < n - 1<p>
 * nums[i] > nums[i + 1]<p>
 * 当数组 nums 中 全局倒置 的数量等于 局部倒置 的数量时，返回 true ；否则，返回 false 。<p>
 *<p>
 * 示例 1：<p>
 * 输入：nums = [1,0,2]<p>
 * 输出：true<p>
 * 解释：有 1 个全局倒置，和 1 个局部倒置。<p>
 *<p>
 * 示例 2：<p>
 * 输入：nums = [1,2,0]<p>
 * 输出：false<p>
 * 解释：有 2 个全局倒置，和 1 个局部倒置。<p>
 *<p>
 * 提示：<p>
 * n == nums.length<p>
 * 1 <= n <= 5000<p>
 * 0 <= nums[i] < n<p>
 * nums 中的所有整数 互不相同<p>
 * nums 是范围 [0, n - 1] 内所有数字组成的一个排列<p>
 */
public class LeetCode0775 {

    @Test
    public void test01() {
        int[] nums = {1,0,2};
//        int[] nums = {1,2,0};
//        int[] nums = {1,0};
        System.out.println(new Solution().isIdealPermutation(nums));
    }
}
class Solution {
    public boolean isIdealPermutation(int[] nums) {
        /**
         * 全局倒置：元素大于后面的其中一个元素
         * 局部倒置：元素大于后一位元素，局部倒置一定属于全局倒置
         * 则本体也可以理解为如果存在非局部倒置即为 false ，数组内所有整数互不相同
         */
        int length = nums.length;
//        for (int i = 0; i < length - 1; i++) {
//            for (int j = i + 2; j < length; j++) {
//                // 除了 i 元素的后一个元素以外，后面的所有元素都需要比 i 元素大才行
//                if (nums[i] > nums[j]) {
//                    // 存在非局部倒置，返回 false
//                    return false;
//                }
//            }
//        }
        /**
         * 针对每一个 nums[i] 判断是否存在一个 j > i + 1 ，使得 nums[i] > nums[j] 成立
         */
        int min = nums[length - 1];
        for (int i = length - 3; i >= 0; i--) {
            // 成立，则代表存在非局部倒置
            if (nums[i] > min) {
                return false;
            }
            min = Math.min(nums[i + 1], min);
        }
        return true;
    }
}
